1 Field of the Invention
The present invention relates to a method of optimizing the arrangement of parts or the like.
2 Description of the Related Art
A part arrangement optimization problem will first be explained. If it is assumed, for example, that the positions for arranging four parts and the number of wires between the respective parts are given as shown in Table 1, the parts arrangement optimization problem is how the parts should be arranged in order to make the total length of wiring the shortest.
TABLE 1 ______________________________________ Number of parts 1 2 3 4 ______________________________________ Number 1 0 3 3 1 of 2 3 0 1 3 parts 3 3 1 0 3 4 1 3 3 0 ______________________________________
Examples of the optimal solution and a non-optimal solution to this problem are shown in FIGS. 4a and 4b, respectively. In FIGS. 4a and 4b, the reference numeral 5 represents a part and 6 a wire. The arrangement shown in FIG. 4a is the optimal arrangement and the arrangement shown in FIG. 4b is an example of a non-optimal solution because the total length of wiring is longer than that in FIG. 4a. There is no analytical solution for the part arrangement optimization problem, and it is necessary to examine all the arrangements in order to attain the optimal solution. However, since there are N! combinations for the arrangement of N parts, if N increases, the calculation time for reaching the optimal solution increases enormously. In other words, the part arrangement optimization problem is a kind of combination optimization problem. Therefore, the object of solving this problem is generally to reach an approximate solution, which is approximate to the optimal solution, at a high speed.
FIG. 5 is a flowchart showing a conventional part arrangement optimization algorithm which is described in Takahashi, W. Balzer, Kyuma: Improvement of Performance of Learning in Boltzmann Machine and Application to Recognition and Optimization Problem (Research Materials for System. Control Study Meeting, the Institute of Electrical Engineers of Japan, SC-91-2, pp. 17 to 18, Mar. 19, 1991), and which uses a Boltzmann machine model, one of the mutual combination type neural network models.
The conventional algorithm will now be explained. This algorithm is used to (approximately) optimize the arrangement of N parts when N parts (part numbers 1 to N) and N positions (position numbers 1 to N) are given. One neuron is allotted to each combination (there are N.sup.2 combinations) of a position number and a part number (step ST13). For example, Table 2 shows an example of the allotment of 4 parts.
TABLE 2 ______________________________________ Position number 1 2 3 4 ______________________________________ Number 1 n.sub.1 n.sub.2 n.sub.3 n.sub.4 of 2 n.sub.5 n.sub.6 n.sub.7 n.sub.7 parts 3 n.sub.9 n.sub.10 n.sub.11 n.sub.12 4 n.sub.13 n.sub.14 n.sub.15 n.sub.16 ______________________________________
The symbol n.sub.i represents an i-th neuron. In this case N.sup.2 neurons are used and the state of each neuron represents whether a certain part is disposed at a certain position. For example, the fact that n.sub.10 is in the excited state (the output of the neuron n.sub.10 is "1") means that the part 3 is disposed at the position 2. This introduces the following restricting conditions to the state of a neuron. That is, since one part can be disposed only at one position at one time, only one of the four neurons in each row in Table 1 can assume the excited state at one time. Since only one part can be disposed at one position at one time, only one of the four neurons in each column in Table 1 can assume the excited state at one time. The weight of a combination between neurons is then determined in accordance with the following equation (step S14): EQU W.sub.ij =c.sub.1 W.sub.ij.sup.c +c.sub.2 W.sub.ij.sup.s ( 1)
The symbol W.sub.ij represents the synaptic weight from a neuron j to i, and c.sub.1 and c.sub.2 are constants. The symbol W.sub.ij.sup.s represents the above-described restricting condition, namely, the suppressive (negative) weight for mutually suppressing the excitation between the neurons in the row and in the column so as to maintain the excited state of only one neuron in one row and in one column. The symbol W.sub.ij.sup.c represents the weight which reflects the total length of wiring, and is obtained from the following equation: EQU W.sub.ij =c.sub.1 W.sub.ig.sup.c +c.sub.2 W.sub.ij.sup.s ( 1)
wherein c.sub.3 is a constant, hp.sub.i,p.sub.j represents the number of wires between parts P.sub.i and p.sub.j, and dq.sub.i,q.sub.j represents the distance between positions q.sub.i and q.sub.j , wherein P.sub.i is the residual when i is divided by N, and q.sub.i is the quotient. If W.sub.ij =W.sub.ji, in a mutual combination type neural network model like this example, the energy E of the network is defined by the following equation: ##EQU1## wherein V.sub.i represents the output (excited state: "1", non-excited state: "0") of the i-th neuron. If the weight W.sub.ij is determined in accordance with the equations (1) and (2), the energy E is represented as follows: EQU E=c.sub.2 .multidot.(total length of wiring)+(constant) (4)
The energy E does not change or is reduced when the state of the neurons are updated. Therefore, when the state of the neurons are updated serially, the state of the network becomes stable in the state in which the energy E is the minimum. The state of the neurons at this time determines the arrangement of the parts which minimizes the energy E and, hence, which makes the total length of wiring the shortest, as is obvious from the equation (4). Actually, the minimal point of the energy is obtained by using a technique called a simulated annealing method, which updates the state of the neurons stochastically in order to avoid the influence of a local stable point (minimal point) of the energy (step S15). The arrangement of the parts is determined on the basis of the state of the neurons at that time (step S16). This arrangement is the (quasi-)optimal solution.
In the conventional part arrangement optimization algorithm described above, since N.sup.2 neurons and N.sup.4 weights are necessary for solving the problem for N parts, if the problem is solved by a computer, the memory capacity and the calculation time which are proportional to N.sup.4 are necessary, so that this algorithm cannot be applied to a large-scale problem in which the number of parts is large.